\chapter{Přepisovací systémy}

V této kapitole si vysvětlíme pojem přepisovací systém a aplikuje dosavadní poznatky o vztahu regulárních jazyků s dobrými předuspořádáními. Přepisovací systémy mají stejnou vyjadřovací sílu jako Turingovy stroje. Nás bude zajímat, za jakých okolností jsou jazyky uzavřené vzhledem k danému přepisovacímu systému regulární. Ukáže se, že přepisovací systémy generují regulární jazyky právě když indukují dobré předuspořádání na slovech nad danou abecedou. Dále se zaměříme na  konkrétní třídy přepisovacích systémů a ukážeme, že indukují dobrá předuspořádání.



\begin{definice}
\emph{Přepisovací systém} je dvojice $(\Sigma, R)$, kde $\Sigma$ je abeceda a $R \subseteq \Sigma^* \times \Sigma^*$ je konečná množina dvojic slov, které se nazývají \emph{přepisovací pravidla}. Pravidlo $(u, v) \in R$ se také zapisuje $u \rightarrow v$, čímž se myslí, že slovo $u$ se přepíše na $v$. Relace $R$ se dá přirozeně rozšířít na další slova nad abecedou $\Sigma$ na relaci $\Rightarrow_R$  podle pravidla:
\[ x \Rightarrow_R y \Longleftrightarrow x=x_1 u x_2  \; \text{ a }  \; y = x_1 v x_2,  \: \text{kde}  \: x_1, x_2 \in \Sigma^*  \: \text{ a }  \: u \rightarrow v        .\]
Konečně reflexivní a tranzitivní uzávěr relace $\Rightarrow_R$ se značí $\Rightarrow_R^*$ a nazývá se \emph{relace odvození}.

\end{definice}

Pro libovolný přepisovací systém $(\Sigma, R)$ je tedy relace odvození $\Rightarrow_R^*$ předuspořádání na množině $\Sigma^*$. Vzhledem k definici relace $\Rightarrow_R^*$ je zřejmé, že je monotónní. Následuje základní tvrzení této kapitoly, které přímo vyplývá z věty \ref{genMyh}.

\begin{veta}
\label{Thue}
Nechť $(\Sigma, R)$ je přepisovací systém a $L$ je jazyk nad abecedou $\Sigma$ uzavřený vzhledem k relaci $\Rightarrow_R^*$. Potom $L$ je regulární, pokud relace $\Rightarrow_R^*$ je dobré předuspořádání. 
\end{veta}

Ve zbytku kapitoly se budeme zaobírat konkrétními  třídami přepisovacích systémů. 

\section{ Bezkontextové přepisovací systémy}
Jako první se zaměříme na unitární přepisovací systémy.

\begin{definice}
Nechť $\Sigma$ je konečná abeceda. Přepisovací systém $(\Sigma, R)$ nazveme \emph{unitární}, pokud množina jeho pravidel je ve tvaru 
\[R=\{\epsilon \rightarrow w | w\in I\},\]
kde $I \subseteq \Sigma^*$ je konečná množina slov. V tom případě je přepisovací systém jasně určen množinou $I$, budeme proto jím indukovanou relaci odvození značit $\Rightarrow_I^*$.
\end{definice}
Přepisování podle pravidel unitárního systému tedy znamená vkládání řetězců z množiny $I$. Je tedy zřejmé, že unitární přepisovací systémy generují bezkontextové jazyky. V našem zájmu bude zjistit, za jakých podmínek jsou jazyky uzavřené na relaci odvození regulární, tedy kdy je $\Rightarrow_I^* $ dobré předuspořádání. Jak se ukáže, musí mít množina $I$ vlastnost nevyhnutelnosti.

\begin{definice}
Nechť $I \subseteq \Sigma^* $. Potom množina $I$ je \emph{nevyhnutelná} (nad abecedou $\Sigma$), pokud existuje přirozené číslo $k$ takové, že libovolné slovo $u \in \Sigma^* $, pro které platí $|u|>k$, je ve tvaru $u = u_1wu_2$ pro $w \in I$ a $u_1, u_2 \in \Sigma^*$. Nejmenší $k$ s touto vlastností nazveme \emph{mez nevyhnutelnosti}.
\end{definice}

Nevyhnutelnost tedy znamená, že libovolné slovo delší než nějaká mez musí jako podřetězec obsahovat nějaké slovo z množiny $I$. Následující tvrzení dává nutnou i postačující podmínku k tomu, aby unitární přepisovací systém indukoval dobré předuspořádání.

\begin{veta}
Nechť $(\Sigma, R)$ je unitární přepisovací systém spolu s množinou $I$. Potom relace odvození $\Rightarrow_I^*$ je dobré předuspořádání právě tehdy, když je množina $I$ nevyhnutelná.
\end{veta}

\begin{proof}
Nevyhnutelnost množiny $I$ je zřejmě nutná podmínka. Aby byla relace $\Rightarrow_I^*$ dobré předuspořádání, nesmí podle definice \ref{wqo}(iv) existovat nekonečná posloupnost neporovnatelných prvků.  Platí-li však $u \Rightarrow_I^* w$, musí slovo $w$ obsahovat podslovo z  množiny $I$. Pokud tedy množina $I$ není nevyhnutelná, existuje nekonečná posloupnost slov neobsahujícíh podslova z množiny $I$ a jsou proto vzájemně neporovnatelná.
\end{proof}





\cleardoublepage

